package leetcode.code1995;

import java.util.HashMap;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 执行用时：10 ms, 在所有 Java 提交中击败了86.50%的用户
 *
 * 内存消耗：37.9 MB, 在所有 Java 提交中击败了9.97%的用户
 *
 * 通过测试用例：211 / 211
 */
public class Solution3 implements IDebug {
	public int countQuadruplets(int[] nums) {
		int len = nums.length;
		int ans = 0;
		int a, b = len - 3, c, d;
		int A, B, C, D;
		Map<Integer, Integer> hash = new HashMap<>();
		while (b >= 1) {// 枚举每一个b，相当于枚举每一个c
			c = b + 1;// c的起始位置比b大1，保证a < b < c < d
			d = c + 1;// d的起始位置比c大1
			B = nums[b];
			C = nums[c];
			while (d < len) {// d去找差，记录下来
				D = nums[d];
				int div = D - C;// 差值
				int count = hash.getOrDefault(div, 0);
				hash.put(div, count + 1);// 差值记录+1
				d++;
			}
			a = 0;
			while (a < b) {// a去找和，去找匹配的差值
				A = nums[a];
				ans += hash.getOrDefault(A + B, 0);// 所有出现的记录都是满足a < b < c < d
				a++;
			}
			b--;
		}
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(4, this.countQuadruplets(HelpDebug.str2array3("[1,1,1,3,5]")));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();

	}

}
